#include "BinarySortTree.h"
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0


BTNode *RotateRight(BTNode *node)
{
    BTNode *t=node->left;
    node->left=t->right;
    t->right=node;
    return t;
}
BTNode *RotateLeft(BTNode *node)
{
    BTNode *t=node->right;
    node->right=t->left;
    t->left=node;
    return t;
}
BTNode *RotateLeftRight(BTNode *node)
{
    node->left=RotateLeft(node->left); 
    return RotateRight(node);
}
BTNode *RotateRightLeft(BTNode *node)
{
    node->right=RotateRight(node->right); 
    return RotateLeft(node);
}
int GetTreeHeight(BTNode *node)
{
    if(node==NULL)
    {
        return 0;
    }
    int leftheight=GetTreeHeight(node->left);
    int rightheight=GetTreeHeight(node->right);
    return (leftheight>rightheight?leftheight:rightheight)+1;

}
BTNode *InsertData(BTNode *node,int data)
{
    BTNode *newnode=(BTNode*)malloc(sizeof(BTNode));
    if(newnode==NULL)
    {
        printf("malloc error\n");
        return NULL;
    }
    newnode->data=data;
    newnode->left=NULL;
    newnode->right=NULL;
    if(node==NULL)
    {
        node=newnode;
    }
    else if(data<node->data)
    {
        node->left=InsertData(node->left,data);
        if(GetTreeHeight(node->left)-GetTreeHeight(node->right)>1)

        {
            if(data<node->left->data)
            {
                node=RotateRight(node);
            }
            else
            {
                node=RotateLeftRight(node);
            }
        }
    }
    else
    {
        node->right=InsertData(node->right,data);
        if(GetTreeHeight(node->left)-GetTreeHeight(node->right)<-1)

        {
            if(data<node->right->data)
            {
                node=RotateRightLeft(node);
            }
            else
            {
                node=RotateLeft(node);
            }
        }
    }
    return node;
}
void InsertNode(LBTree *tree, ElementType element)
{
    tree->root=InsertData(tree->root,element);
}



BTNode *CreateTreeNode(ElementType element)
{
    BTNode *treenode=(BTNode*)malloc(sizeof(BTNode));
    if(treenode==NULL)
    {
        printf("tree node malloc error\n");
        return NULL;
    }
    treenode->data=element;
    treenode->left=NULL;
    treenode->right=NULL;
    // treenode->parent=NULL;
    return treenode;
}
//初始化
int InitLBTree(LBTree *tree,ElementType element)
{
    tree->root=CreateTreeNode(element);//给根申请内存并初始化
    if(tree->root==NULL)
    {
        printf("InitLbtree error\n");
        return false;
    }
    else
        return true;
}

// //数据插入
// void Insert(BTNode *node,ElementType element)
// {
//     if(node->data==element)
//         return;
//     if(node==NULL)
//     {
//         return;
//     }
//     if(node->left==NULL&&element<node->data)//小于node->data插左边
//     {
//         node->left=CreateTreeNode(element);
//         node->left->parent=node;//将创建的节点的父节点指向自己
//         return;
//     }
//     if(node->right==NULL&&element>node->data)//大于node->data插右边
//     {
//         node->right=CreateTreeNode(element);
//         node->right->parent=node;//将创建的节点的父节点指向自己
//         return;
//     }
//     //没位置插入往下递归
//     if(element<node->data)
//     {
//         Insert(node->left,element);
//     }
//     else if(element>node->data)
//     {
//         Insert(node->right,element);
//     }
// }



// void InsertNode(LBTree *tree, ElementType element)
// {
//     Insert(tree->root,element);
// }
//中序遍历
void MidPrint(BTNode *node)
{
    if(node!=NULL)
    {
        MidPrint(node->left);
        printf("%d ",node->data);
        MidPrint(node->right);
    } 
}
void MidTravel(LBTree *tree)
{
    MidPrint(tree->root);
    printf("\n");
}
//前序遍历
void PrevPrint(BTNode *node)
{
    if(node!=NULL)
    {
        printf("%d ",node->data);
        PrevPrint(node->left);
        PrevPrint(node->right);
    }
    
}
void PrevTravel(LBTree *tree)
{
    PrevPrint(tree->root);
    printf("\n");
}
//后序遍历
void PostPrint(BTNode *node)
{
    if(node!=NULL)
    {
        PostPrint(node->left);
        PostPrint(node->right);
        printf("%d ",node->data);
    } 
}
void PostTravel(LBTree *tree)
{
    PostPrint(tree->root);
    printf("\n");
}
//根据数据找节点
BTNode *SearchNode(BTNode *node,ElementType element)
{
    if(node==NULL)
    {
        return NULL;
    }
    if(node->data==element)//node->data==element直接返回该节点
    {
        return node;
    }
    else if(node->data<element)
    {
        return SearchNode(node->right,element);//node->data<element往左遍历
    }
    else if(node->data>element)
    {
        return SearchNode(node->left,element);//node->data>element往尤遍历
    }
}
BTNode *SearchElement(LBTree *tree, ElementType element)
{
    return SearchNode(tree->root,element);
}
// //数据删除
// void DeleteElement(LBTree *tree, ElementType element)
// {
//     BTNode *targetnode=SearchNode(tree->root,element);//记下要删除的节点
//     if(targetnode==NULL)
//     {
//         return;
//     }
//     if(targetnode->left==NULL&&targetnode->right==NULL&&targetnode->parent==NULL)//如果为根节点，并且左右都为空
//     {
//         tree->root=NULL;
//         free(targetnode);
//         return;
//     }
//     else if(targetnode->left==NULL&&targetnode->right==NULL)//如果不是根节点，但是左右都为空
//     {
//         if(targetnode->parent->left==targetnode)//判断该节点是否为该节点的父节点的左节点
//             targetnode->parent->left=NULL;
//         else
//             targetnode->parent->right=NULL;
//         free(targetnode);
//     }
//     else if(targetnode->right==NULL)//如果右节点为空
//     {
//         targetnode->left->parent=targetnode->parent;
//         if(targetnode->parent==NULL)//如果为根节点
//             tree->root=targetnode->left;
//         else if(targetnode->parent->left==targetnode)//如果该节点的父节点的左节点等于该节点 
//             targetnode->parent->left=targetnode->left;
//         else
//             targetnode->parent->right=targetnode->left;   
//         free(targetnode);
//     }
//     else if(targetnode->left==NULL) //如果该节点的左节点为空
//     {
//         targetnode->right->parent=targetnode->parent;
//         if(targetnode->parent==NULL)//如果为根节点
//             tree->root=targetnode->right;
//         else if(targetnode->parent->right==targetnode)//如果该节点的父节点的右节点等于该节点
//             targetnode->parent->right=targetnode->right;
//         else
//             targetnode->parent->left=targetnode->right;
//         free(targetnode);
//     }
//     else if(targetnode->left!=NULL&&targetnode->right!=NULL)//如果该节点的左右节点都不为空
//     {
//         BTNode *minnode=targetnode->right;//记下该节点的右节点
//         while(minnode->left!=NULL)//为空截至
//         {
//             minnode=minnode->left;//向左遍历
//         }
//         targetnode->data=minnode->data;
//         if(minnode->parent!=targetnode)//如果minnode->parent!=targetnode
//         {
//             minnode->parent->left=minnode->right;//挂左边
//             if(minnode->right!=NULL)
//                 minnode->right->parent=minnode->parent;
//         }
//         else
//         {
//             targetnode->right=minnode->right;//挂右边
//             if(minnode->right!=NULL)
//                 minnode->right->parent=minnode->parent;
//         }
//         free(minnode);
//     }
// }

void FreeBTNode(BTNode *node)
{
    if(node==NULL)
        return;
    FreeBTNode(node->left);//左遍历
    FreeBTNode(node->right);//右遍历
    free(node);//释放自己
}
void FreeLBTree(LBTree *tree)
{
    FreeBTNode(tree->root);
    tree->root=NULL;
}
